package com.tgy.algorithm.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class NodeRandom {
    int val;
    NodeRandom next;
    NodeRandom random;
    NodeRandom(int val) {
        this.val = val;
    }
}

public class _copy_rand_link_01 {

    public static NodeRandom generalRandomLink() {

        NodeRandom header = new NodeRandom(1);
        NodeRandom node01 = new NodeRandom(2);
        header.next = node01;
        NodeRandom node02 = new NodeRandom(3);
        node01.next = node02;
        NodeRandom node03 = new NodeRandom(4);
        node02.next = node03;

        header.random = node03;
        node01.random = node02;
        node02.random = header;
        node03.random = node01;

        return header;
    }

    public static NodeRandom copyRandomLink(NodeRandom header) {

        if (header == null) {
            return null;
        }

        HashMap<NodeRandom, NodeRandom> map = new HashMap<>();
        NodeRandom node = header;
        while (node != null) {
            map.put(node, new NodeRandom(node.val));
            node = node.next;
        }

        NodeRandom retNode = map.get(header);
        node = header;
        while (node != null) {
            NodeRandom newNode = map.get(node);
            if (node.next != null) {
                newNode.next = map.get(node.next);
            }
            if (node.random != null) {
                newNode.random = map.get(node.random);
            }
            node = node.next;
        }

        return retNode;
    }

    public static NodeRandom copyRandomLink01(NodeRandom header) {

        if (header == null) {
            return null;
        }

        ArrayList<Object> objects = new ArrayList<>();

        NodeRandom node = header;
        while (node != null) {
            NodeRandom newNode = new NodeRandom(node.val);
            newNode.next = node.next;
            node.next = newNode;
            node = newNode.next;
        }

        // 设置random指针
        NodeRandom preNode = header;
        NodeRandom postNode = header.next;
        while (postNode != null) {
            postNode.random = preNode.random != null ? preNode.random.next:null;
            preNode = postNode.next;
            postNode = preNode != null ? preNode.next:null;
        }

        // 恢复原来的链表
        preNode = header;
        postNode = header.next;
        NodeRandom retNode = postNode;
        while (postNode != null) {
            preNode.next  = postNode.next;
            postNode.next =postNode.next != null ? postNode.next.next:null;
            preNode = preNode.next;
            postNode = postNode.next;
        }

        return retNode;
    }

    public static boolean isEqualRandomLink(NodeRandom node1, NodeRandom node2) {

        while (true) {
            if (node1 == null && node2 != null) {
                return false;
            }
            if (node1 != null && node2 == null) {
                return false;
            }

            if (node1 == null && node2 == null) {
                break;
            }

            if (node1.val != node2.val) {
                return false;
            }

            if (node1.random != null && node2.random == null) {
                return false;
            }else if (node1.random == null && node2.random != null) {
                return false;
            }else if (node1.next != null && node2.next != null && node1.random.val != node2.random.val){
                return false;
            }

            node1 = node1.next;
            node2 = node2.next;
        }

        return true;
    }

    public static void main(String[] args) {
        NodeRandom nodeRandom = generalRandomLink();
        NodeRandom nodeRandom1 = copyRandomLink01(nodeRandom);
//        printRandomLink(nodeRandom1);
        boolean isEqual = isEqualRandomLink(nodeRandom, nodeRandom1);
        System.out.println(isEqual);
    }
}
